// insert here for test
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
// insert end
#include <algorithm> // find
#include <cstdlib>
#include <ctime>
#include <iostream> // cin cout endl
#include <utility>  // pair

#include <malloc.h> // malloc_trim

#include "print.hpp" // for print
#include "test.h"

using std::cin;
using std::cout;
using std::endl;

// 红黑树实现
// 元素 key 不能重复
using std::map;
using std::set;
// 元素 key 可以重复
using std::multimap;
using std::multiset;

using std::pair;

// hash_table 实现
// 元素 key 不能重复
using std::unordered_map;
using std::unordered_set;
// 元素 key 可以重复
using std::unordered_multimap;
using std::unordered_multiset;

const long STRING_LENGTH = 10;

// 元素不可重复
void test_set(const long &value) {
    print("test_set()...");
    set<string> c;
    print("start inserting...");
    TimeCounter t;
    for (long i = 0; i < value; ++i) {
        c.insert(get_a_random_string(STRING_LENGTH));
    }
    t.endAndShow();
    print("set.size() = ", c.size());
    print("set.max_size() = ", c.max_size());

    string target = get_a_target_string();
    {
        print("start finding...", "std::find(): ");
        t.start();
        auto pItem = std::find(c.begin(), c.end(), target);
        t.endAndShow();
        if (pItem != c.end()) {
            print("found ", *pItem);
        } else {
            print("sorry, not found");
        }
    }

    {
        print("set.find(): ");
        t.start();
        auto pItem = c.find(target);
        t.endAndShow();
        if (pItem != c.end()) {
            print("found ", *pItem);
        } else {
            print("sorry, not found");
        }
    }
}

// 元素可重复
void test_multiset(const long &value) {
    print("test_multiset() ...");
    multiset<string> c;
    print("start inserting...");
    TimeCounter t;
    for (long i = 0; i < value; ++i) {
        c.insert(get_a_random_string(STRING_LENGTH));
    }
    t.endAndShow();
    print("multiset.size: ", c.size());
    print("multiset.max_size: ", c.max_size());

    print("start finding: ");
    string target = get_a_target_string();
    {
        print("using std::find");
        t.start();
        auto pItem = std::find(c.begin(), c.end(), target);
        t.endAndShow();
        if (pItem != c.end()) {
            print("found, ", *pItem);
        } else {
            print("sorry, not found");
        }
    }

    {
        print("using multiset.find()");
        t.start();
        auto pItem = c.find(target);
        t.endAndShow();
        if (pItem != c.end()) {
            print("found, ", *pItem);
        } else {
            print("sorry, not found");
        }
    }
}

void test_map(const long &value) {
    print("test_map()...");
    map<long, string> c;
    print("start inserting...");
    TimeCounter t;
    for (long i = 0; i < value; ++i) {
        // map 可以使用 []
        c[i] = get_a_random_string(STRING_LENGTH);
    }
    t.endAndShow();
    print("map.size() = ", c.size());
    print("map.max_size() = ", c.max_size());

    // copy form multimap
    // 这个查找意义不大
    print("start finding: ");
    long target = get_a_target_long();
    t.start();
    auto pItem = c.find(target);
    t.endAndShow();

    if (pItem != c.end()) {
        // map 取值 .second
        print("found, value", pItem->second);
    } else {
        print("sorry, not found");
    }
}

// 红黑树实现 multimap 键可重复
void test_multimap(const long &value) {
    print("test_multimap()...");
    multimap<long, string> c;
    print("start inserting...");
    TimeCounter t;
    for (long i = 0; i < value; ++i) {
        // multimap 不能使用 [] 做 insertion
        c.insert(pair<long, string>(i, get_a_random_string(STRING_LENGTH)));
    }
    t.endAndShow();
    print("multimap.size(): ", c.size());
    print("multimap.max_size(): ", c.max_size());

    print("start finding: ");
    long target = get_a_target_long();
    t.start();
    auto pItem = c.find(target);
    t.endAndShow();

    if (pItem != c.end()) {
        print("found, value", pItem->second);
    } else {
        print("sorry, not found");
    }
}

// unordered_* 哈希表实现

// copy from set
void test_unordered_set(const long &value) {
    print("test_unordered_set()...");
    unordered_set<string> c;
    print("start inserting...");
    TimeCounter t;
    for (long i = 0; i < value; ++i) {
        c.insert(get_a_random_string(STRING_LENGTH));
    }
    t.endAndShow();
    print("unordered_set.size() = ", c.size());
    print("unordered_set.max_size() = ", c.max_size());

    string target = get_a_target_string();
    {
        print("start finding...", "std::find(): ");
        t.start();
        auto pItem = std::find(c.begin(), c.end(), target);
        t.endAndShow();
        if (pItem != c.end()) {
            print("found ", *pItem);
        } else {
            print("sorry, not found");
        }
    }

    {
        print("unordered_set.find(): ");
        t.start();
        auto pItem = c.find(target);
        t.endAndShow();
        if (pItem != c.end()) {
            print("found ", *pItem);
        } else {
            print("sorry, not found");
        }
    }
}

void test_unordered_multiset(const long &value) {
    print("test_unordered_multiset()...");
    unordered_multiset<string> c;

    print("start inserting: ");
    TimeCounter t;
    for (long i = 0; i < value; ++i) {
        c.insert(get_a_random_string(STRING_LENGTH));
    }
    t.endAndShow();

    print("unordered_multiset.size() = ", c.size());
    print("unordered_multiset.max_size() = ", c.max_size());
    print("unordered_multiset.bucket_count() = ", c.bucket_count());
    print("unordered_multiset.load_factor() = ", c.load_factor());
    print("unordered_multiset.max_load_factor() = ", c.max_load_factor());
    print("unordered_multiset.max_bucket_count() = ", c.max_bucket_count());

    print("---- bucket_size ----");
    for (size_t i = 0; i < 20; ++i) {
        print("bucket #", i, " has ", c.bucket_size(i), " elements");
    }
    print("---- bucket_sizes end ----");

    string target = get_a_target_string();
    {
        print("start finding: ", "std::find()...");
        t.start();
        auto pItem = std::find(c.begin(), c.end(), target);
        t.endAndShow();
        if (pItem != c.end()) {
            print("found, ", *pItem);
        } else {
            print("sorry, not found");
        }
    }

    {
        print("unordered_multiset.find...");
        t.start();
        auto pItem = c.find(target);
        t.endAndShow();
        if (pItem != c.end()) {
            print("found, ", *pItem);
        } else {
            print("sorry, not found");
        }
    }
}

// copy from map
void test_unordered_map(const long &value) {
    print("test_unordered_map()...");
    unordered_map<long, string> c;
    print("start inserting...");
    TimeCounter t;
    for (long i = 0; i < value; ++i) {
        // unordered_map 可以使用 []
        c[i] = get_a_random_string(STRING_LENGTH);
    }
    t.endAndShow();
    print("unordered_map.size() = ", c.size());
    print("unordered_map.max_size() = ", c.max_size());

    // copy form multiunordered_map
    // 这个查找意义不大
    print("start finding: ");
    long target = get_a_target_long();
    t.start();
    auto pItem = c.find(target);
    t.endAndShow();

    if (pItem != c.end()) {
        print("found, value", pItem->second);
    } else {
        print("sorry, not found");
    }
}

// copy form multimap
void test_unordered_multimap(const long &value) {
    print("test_unordered_multimap()...");
    // 配对类型
    unordered_map<long, string> c;
    print("start inserting...");
    TimeCounter t;
    for (long i = 0; i < value; ++i) {
        // multimap 不能使用 [] 做 insertion
        c.insert(pair<long, string>(i, get_a_random_string(STRING_LENGTH)));
    }
    t.endAndShow();
    print("unordered_multimap.size(): ", c.size());
    print("unordered_multimap.max_size(): ", c.max_size());

    print("start finding: ");
    long target = get_a_target_long();
    t.start();
    auto pItem = c.find(target);
    t.endAndShow();

    if (pItem != c.end()) {
        print("found, value", pItem->second);
    } else {
        print("sorry, not found");
    }
}

void menu() {
    print(cout, "Enter a number as option:", "1. test_set;", "2. test_map;",
            "3. test_multiset;", "4. test_multimap;", "5. test_unordered_set;",
            "6. test_unordered_map;", "7. test_unordered_multiset;",
            "8. test_unordered_multimap;", "q. end;", "You choose: ");
}

int main(void) {
    print("start...");
    const long value = get_a_target_long();

    menu();
    char option;
    while (cin >> option) {
        switch (option) {
            case '1':
                print("---");
                test_set(value);
                print("---");
                break;
            case '2':
                print("---");
                test_map(value);
                print("---");
                break;
            case '3':
                print("---");
                test_multiset(value);
                print("---");
                break;
            case '4':
                print("---");
                test_multimap(value);
                print("---");
                break;
            case '5':
                print("---");
                test_unordered_set(value);
                print("---");
                break;
            case '6':
                print("---");
                test_unordered_map(value);
                print("---");
                break;
            case '7':
                print("---");
                test_unordered_multiset(value);
                print("---");
                break;
            case '8':
                print("---");
                test_unordered_multimap(value);
                print("---");
                break;
            case 'q':
                print("buy!");
                return 0;
            default:
                print("wrong option");
                break;
        }
        malloc_trim(0);
        menu();
    }

    return 0;
}
